package binaryTree;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * @author kunkun
 * @className LeetCode_437
 * @Description ...
 * @date 2025/3/15 15:03
 */
public class LeetCode_437 {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public int pathSum(TreeNode root, int targetSum) {
        if (root == null) return 0;
        // 计算以当前节点为起点的路径数 + 递归处理左右子树
        return countPath(root, targetSum)
                + pathSum(root.left, targetSum)
                + pathSum(root.right, targetSum);
    }

    private int countPath(TreeNode node, long target) {
        if (node == null) return 0;
        int res = 0;
        if (node.val == target) {
            res++;
        }
        // 继续向左右子树累加，寻找可能的路径
        res += countPath(node.left, target - node.val);
        res += countPath(node.right, target - node.val);
        return res;
    }


}
